package code;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class NextRightPointers {
	static public class TreeLinkNode {
	     int val;
	     TreeLinkNode left, right, next;
	     TreeLinkNode(int x) {
	    	 	val = x; 
	    	 }
	}
	
    public void connect(TreeLinkNode root) {
        Queue<TreeLinkNode> queue=new LinkedList<TreeLinkNode>();
        Map<TreeLinkNode,Integer> map=new HashMap<TreeLinkNode,Integer>();
        queue.add(root);
        map.put(root, 0);
        while(!queue.isEmpty()){
        	TreeLinkNode head=queue.poll();
        	int level=map.get(head);
        	TreeLinkNode nextNode=queue.peek();
        	//不为下一个相邻的节点空，或不在同一层
        	if(nextNode==null || level!=map.get(nextNode)){
        		head.next=null;
        	}
        	else //在同一层
        		head.next=nextNode;
        	if(head.left!=null){
        		queue.add(head.left);
        		map.put(head.left, level+1);
        	}
        	if(head.right!=null){
        		queue.add(head.right);
        		map.put(head.right, level+1);
        	}
        }
    }
	
    public static void main(String args){
    	
    }
}
